package com.captain.special.链表;

import com.captain.leetcode.链表.ListNode;

import java.util.ArrayList;
import java.util.List;

/**
 * Des:
 *
 * @author XL
 * @Date 2022/3/24 11:26
 */
public class 重排链表143 {
    //1 2 3 4 5
    //1 5 2 4 3
    public static void main(String[] args) {
        new 重排链表143().reorderList(ListNode.getInstance());

    }

    public void reorderList(ListNode head) {
        //利用集合将链表进行存储
        if (head == null) return;
        List<ListNode> list = new ArrayList<>();
        while (head != null) {
            list.add(head);
            head = head.next;
        }
        int i = 0, j = list.size() - 1;
        while (i < j) {
            list.get(i).next = list.get(j);
            i++;
            if (i == j) {
                break;
            }
            list.get(j).next = list.get(i);
            j--;
        }
        //处理最后一个节点
        list.get(i).next = null;

        //解法二:1.快慢指针查找中间节点  2.反转链表  3.链表合并

    }

    private ListNode flip(ListNode head) {
        ListNode pre = null;
        while (head != null) {
            ListNode temp = head.next;
            head.next = pre;
            pre = head;
            head = temp;
        }
        return pre;
    }
}
